﻿using System.Collections;

namespace KinonekoSoftware.Extensions.Collections
{
    public class BucketList<T> : IList<T>
    {
        private const int DefaultBucketSize = 255;
        private const int MinimumBucketSize = 64;
        private const int MaximumBucketSize = 8096;
        
        private readonly int           BucketSize;
        private readonly List<List<T>> Buckets;

        private int _version;
        private int _count;
        private int _currentBucket;
        
        /// <summary>
        /// 
        /// </summary>
        public BucketList() : this(DefaultBucketSize){}

        /// <summary>
        /// 
        /// </summary>
        /// <param name="bucketSize"></param>
        public BucketList(int bucketSize)
        {
            BucketSize = GetValidBucketSize(bucketSize);
            Buckets    = new List<List<T>>();
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="collection"></param>
        /// <param name="bucketSize"></param>
        public BucketList(IEnumerable<T> collection, int bucketSize = DefaultBucketSize) : this(bucketSize)
        {
            //
            //
            AddRange(collection);
        }
        
        public static int GetValidBucketSize(int size) => Math.Clamp(size, MinimumBucketSize, MaximumBucketSize);

        private void Merge()
        {
            if (Buckets.Count < 3)
            {
                return;
            }
            
            for (var i = 0; i < Buckets.Count; i++)
            {
                var bucket = Buckets[i];
                var remain = BucketSize - bucket.Count;

                if (remain > 0)
                {
                    var iterator = Buckets[i + 1].GetRange(0, remain);
                    
                    //
                    //
                    Buckets[i+1].RemoveRange(0, remain);
                    
                    //
                    //
                    bucket.AddRange(iterator);
                }
            }

            _version++;
        }
        
        public void Add(T item)
        {
            if (Buckets.Count == 0)
            {
                Buckets.Add(new List<T>{ item});
                _currentBucket = 0;
            }
            else if (Buckets[_currentBucket].Count >= BucketSize)
            {
                //
                // 如果总Bucket数大于_currentBucket
                // 并且下一个Bucket能容纳新元素，则添加到下一个Bucket
                //
                // notice:
                // 可能会因为整理Bucket，导致部分的Bucket是空的或者未占满。
                if (_currentBucket < Buckets.Count && Buckets[++_currentBucket].Count < BucketSize)
                {
                    Buckets[_currentBucket].Add(item);
                }
                else
                {
                    Buckets.Add(new List<T>{ item});
                    _currentBucket++;
                }
            }
            else
            {
                Buckets[_currentBucket].Add(item);
            }

            _count++;
            _version++;
        }

        public void AddRange(IEnumerable<T> collection)
        {
            if (collection is ICollection<T> collection2)
            {
                var remain = BucketSize - Buckets[_currentBucket].Count;
                
                //
                // 如果要添加的集合也不能填满当前Bucket
                // 直接调用AddRange
                if (remain >= collection2.Count)
                {
                    Buckets[_currentBucket].AddRange(collection2);
                }
                else
                {
                    var array   = new T[remain];
                    var remain2 = Math.Clamp(collection2.Count - remain, 1, BucketSize);

                    //
                    //
                    collection2.CopyTo(array, 0);
                    Buckets[_currentBucket].AddRange(array);
                    
                    //
                    //
                    array = new T[BucketSize];

                    while (remain2 > 0)
                    {
                        //
                        // 复制到新的数组
                        collection2.CopyTo(array, remain);

                        //
                        // 新建新的Bucket
                        var bucket = new List<T>(array);

                        //
                        //
                        Buckets.Add(bucket);
                        _currentBucket++;
                        
                        //
                        //
                        remain  += remain2;
                        remain2 =  Math.Clamp(collection2.Count - remain, 1, BucketSize);
                    }
                }
                
                
                _count += collection2.Count;
                _version++;
            }
            else
            {
                foreach (var item in collection)
                {
                    Add(item);
                }
            }
        }

        public void Clear()
        {
            foreach (var bucket in Buckets)
            {
                bucket.Clear();
            }
            
            //
            //
            Buckets.Clear();
            _currentBucket = 0;
            _version++;
            _count = 0;
        }

        public bool Contains(T item)
        {
            return Buckets.Any(
                               x => x.Any(
                                          y => EqualityComparer<T>.Default
                                                                  .Equals(y, item)));
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            
            ArgumentNullException.ThrowIfNull(array);

            if (arrayIndex < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(arrayIndex));
            }

            if (arrayIndex >= _count)
            {
                throw new ArgumentOutOfRangeException($"arrayIndex: {arrayIndex} 不允许大于等于{_count}");
            }

            if (array.Length - arrayIndex < _count)
            {
                throw new ArgumentOutOfRangeException($"arrayIndex - array.Length的长度后不应该小于_count");
            }

            foreach (var bucket in Buckets)
            {
                if (bucket.Count > 0)
                {
                    bucket.CopyTo(array, arrayIndex);
                    arrayIndex += bucket.Count;
                }
                else
                {
                    break;
                }
            }
        }
        
        public bool Remove(T item)
        {
            var index = IndexOf(item);

            if (index < 0)
            {
                return false;
            }
            
            RemoveAt(index);
            return true;
        }

        public void Insert(int index, T item)
        {
            
        }

        public void RemoveAt(int index)
        {
            var bucketIndex  = index / BucketSize;
            var bucketNumber = index % BucketSize;
            
            //
            //
            Buckets[bucketIndex].RemoveAt(bucketNumber);

            //
            //
            _version++;
            _count--;
            
            //
            // 数量小于 1/2，Massive程度非常高，需要重新整理。
            if (Buckets[bucketIndex].Count < (BucketSize / 2))
            {
                Merge();
            }

        }
        
        public int IndexOf(T item)
        {
            var index = 0;
            
            foreach (var i in Buckets.SelectMany(bucket => bucket))
            {
                if (EqualityComparer<T>.Default.Equals(item, i))
                {
                    return index;
                }
                
                index++;
            }

            return -1;
        }

        public int            Count           => _count;
        public bool           IsReadOnly      => false;

        public IEnumerator<T> GetEnumerator()
        {
            if (Buckets.Count == 0)
            {
                yield break;
            }

            foreach (var item in Buckets.SelectMany(x => x))
            {
                yield return item;
            }
        }

        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();




        public T this[int index]
        {
            get
            {
                
                if (index < 0)
                {
                    throw new ArgumentOutOfRangeException(nameof(index));
                }

                if (index >= _count)
                {
                    throw new ArgumentOutOfRangeException($"arrayIndex: {index} 不允许大于等于{_count}");
                }

                var bucketIndex  = index / BucketSize;
                var bucketNumber = index % BucketSize;
                return Buckets[bucketIndex][bucketNumber];
            }
            set
            {
                
                if (index < 0)
                {
                    throw new ArgumentOutOfRangeException(nameof(index));
                }

                if (index >= _count)
                {
                    throw new ArgumentOutOfRangeException($"arrayIndex: {index} 不允许大于等于{_count}");
                }
                
                var bucketIndex  = index / BucketSize;
                var bucketNumber = index % BucketSize;
                Buckets[bucketIndex][bucketNumber] = value;
            }
        }
    }
}